class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = needle.length();
        int nextval[10001];
        int i = 0,j = 0;
        GetNextval(needle,nextval);
        while(i < haystack.length() && j < n)
        {
            if(j == -1 || haystack[i] == needle[j])
            {
                i++;
                j++;
            }
            else j = nextval[j];
        }
        if(j >= n) return (i - n);
        else return -1;
    }

    void GetNextval(string s,int nextval[])
    {
        int j = 0,k = -1;
        nextval[0] = -1;
        while(j < s.length())
        {
            if(k == -1 ||s[j] == s[k])
            {
                k++;
                j++;
                if(s[j] != s[k])
                    nextval[j] = k;
                else
                    nextval[j] = nextval[k];
            }
            else k = nextval[k];
        }
    }
};
